package uestc.lj.midPromotion.dfs;

import java.util.HashMap;

/**
 * @Author:Crazlee
 * @Date:2021/12/4
 */
public class Code11_PreAndInArrayToPosArray {
	public static int[] getPostArray(int[] preArray, int[] inorderArray) {
		if (preArray == null || inorderArray == null) {
			return null;
		}
		int length = preArray.length;
		int[] postArray = new int[length];
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < length; i++) {
			map.put(inorderArray[i], i);
		}
		setPostArray(preArray, 0, length - 1,
				inorderArray, 0, length - 1,
				postArray, 0, length - 1, map);
		return postArray;
	}

	private static void setPostArray(int[] preArray, int prei, int prej,
	                                 int[] inorderArray, int ini, int inj,
	                                 int[] postArray, int posti, int postj,
	                                 HashMap<Integer, Integer> map) {
		if (prei > prej) {
			return;
		}
		if (prei == prej) {
			postArray[posti] = preArray[prei];
		}
		//前序的第一个节点就是后序的最后一个节点
		postArray[postj] = preArray[prei];
		//寻找前序第一个节点在中序的位置
		int find = map.get(preArray[prei]);
		setPostArray(preArray, prei + 1, prei + find - ini,
				inorderArray, ini, find - 1,
				postArray, posti, posti + find - ini - 1, map);

		setPostArray(preArray, prei + find - ini + 1, prej,
				inorderArray, find + 1, inj,
				postArray, posti + find - ini, postj - 1, map);
	}

	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] pre = {1, 2, 4, 5, 3, 6, 7};
		int[] in = {4, 2, 5, 1, 6, 3, 7};
		int[] pos = getPostArray(pre, in);
		printArray(pos);
	}
}

